
#include <iostream>
#include <list>
#include <numeric>
#include <queue>
#include <unordered_map>
using namespace std;

class LRUCache
{
    using PII = pair<int, int>;
public:
    LRUCache(int capacity)
        : _capacity(capacity)
    {}

    int get(int key)
    {
        if (!_hash.count(key))
            return -1;

        auto cur = *_hash[key];
        _ls.erase(_hash[key]);
        _ls.push_back(cur);
        _hash[key] = --_ls.end();

        return cur.second;
    }

    void put(int key, int value)
    {
        if (-1 == get(key))
        {
            if (_ls.size() == _capacity)
            {
                _hash.erase(_ls.front().first);
                _ls.pop_front();
            }
            _ls.push_back({ key, value });
            _hash[key] = --_ls.end();
        }
        else
        {
            _hash[key]->second = value;
        }
    }

private:
    int _capacity = 0;
    list<PII> _ls;
    unordered_map<int, list<PII>::iterator> _hash;
};

class Solution
{
public:
    int countStudents1(vector<int>& students, vector<int>& sandwiches)
    {
        int s1 = accumulate(students.begin(), students.end(), 0);
        int s0 = students.size() - s1;

        for (int i = 0; i < sandwiches.size(); ++i)
        {
            if (sandwiches[i] && s1 > 0)
                --s1;
            else if (sandwiches[i] < 1 && s0 > 0)
                --s0;
            else
                break;
        }

        return s0 + s1;
    }

    int countStudents2(vector<int>& students, vector<int>& sandwiches)
    {
        int sum = 0;
        queue<int> q;
        vector<int> st = { sandwiches.rbegin(), sandwiches.rend() };

        for (const auto& e : students)
        {
            sum += e;
            q.push(e);
        }

        while (q.size() && st.size())
        {
            int front = q.front();

            if (front != st.back())
            {
                q.pop();
                q.push(front);
            }
            else
            {
                sum -= front;
                q.pop();
                st.pop_back();
            }

            if (q.size() && ((0 == sum && 1 == st.back()) || (q.size() == sum && 0 == st.back())))
                return q.size();
        }

        return 0;
    }

    int countStudents3(vector<int>& students, vector<int>& sandwiches)
    {
        int cnt[2] = { 0 };

        for (const auto& e : students)
        {
            ++cnt[e];
        }
        for (const auto& e : sandwiches)
        {
            if (cnt[e])
                --cnt[e];
            else
                break;
        }

        return cnt[0] + cnt[1];
    }
};

void Test1()
{
    LRUCache obj(2);

    obj.put(1, 1);
    obj.put(2, 2);
    cout << obj.get(1) << endl;
    obj.put(3, 3);
    cout << obj.get(2) << endl;
    obj.put(4, 4);
    cout << obj.get(1) << endl;
    cout << obj.get(3) << endl;
    cout << obj.get(4) << endl;
}

int main()
{
    Test1();

	return 0;
}